package com.alex.space.commons;

import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.time.StopWatch;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Alex
 *         Created by Alex on 2017/12/21.
 *         <p>
 *         排序实现
 */
public class SortUtils {

    private static final int ARRAY_SIZE = 100;
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {

        int[] num = generateRandomArray();
        printArray(num);
        stopWatch.start();

//        insertionSort(num);
//        mergeSort(num);
//        quickSort(num);
//        countSort(num);
//        radixSort(num, 100000);
//        radixSort(num, 10, 4);
        heap_sort(num);

        printArray(num);
        stopWatch.stop();
        System.out.println("time is " + stopWatch.getTime());

//        for (int n : num) {
//            System.out.printf(n + "\t");
//        }
    }

    private static int[] generateRandomArray() {
        int[] num = new int[ARRAY_SIZE];
        for (int i = 0; i < ARRAY_SIZE; i++) {
            num[i] = RandomUtils.nextInt(0, ARRAY_SIZE);
        }
        return num;
    }

    /**
     * 插入排序
     */
    public static void insertionSort(int[] num) {
        int key;
        for (int j = 2; j < num.length; j++) {
            key = num[j];
            int i = j;
            for (; i > 0 && key < num[i - 1]; i--) {
                num[i] = num[i - 1];
            }
            num[i] = key;
        }
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] num) {
        innerSort(num, 0, num.length - 1);
    }

    private static void innerSort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }

        int center = (left + right) / 2;
        innerSort(data, left, center);
        innerSort(data, center + 1, right);
        innerMerge(data, left, center, right);
    }

    /**
     * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
     *
     * @param data   数组对象
     * @param left   左数组的第一个元素的索引
     * @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
     * @param right  右数组最后一个元素的索引
     */
    private static void innerMerge(int[] data, int left, int center, int right) {

        // 临时数组
        int[] tmpArr = new int[data.length];
        // 右数组第一个元素索引
        int mid = center + 1;
        // third 记录临时数组的索引
        int third = left;
        // 缓存左数组第一个元素的索引
        int tmp = left;
        while (left <= center && mid <= right) {
            // 从两个数组中取出最小的放入临时数组
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }

        // 将临时数组中的内容拷贝回原数组中
        // （原left-right范围的内容被复制回原数组）
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] num) {
        innerQuickSort(num, 0, num.length - 1);
    }

    private static void innerQuickSort(int[] num, int low, int high) {
        if (low < high) {
//            int middle = partition(num, low, high);
            int middle = randomPartition(num, low, high);
            innerQuickSort(num, low, middle - 1);
            innerQuickSort(num, middle + 1, high);
        }
    }

    /**
     * 获取中点
     * 并保证中点左侧的数都小于中点，中点右侧的数都大于中点
     *
     * @param num  待排序数组
     * @param low  起点
     * @param high 终点
     */
    public static int partition(int[] num, int low, int high) {
        int temp = num[low];
        int i = low, j = high;
        while (i != j) {
            while (num[j] >= temp && i < j) {
                j--;
            }

            while (num[i] <= temp && i < j) {
                i++;
            }

            if (i < j) {
                int t = num[i];
                num[i] = num[j];
                num[j] = t;
            }
        }
        num[low] = num[i];
        num[i] = temp;

        return i;
    }

    /**
     * 随机快速排序
     * 加入随机数参数器
     */
    public static int randomPartition(int[] num, int low, int high) {
        int i = new Random().nextInt(high - low) + low;

        int temp = num[i];
        num[i] = num[low];
        num[low] = temp;

        return partition(num, low, high);
    }

    /**
     * 计数排序
     * 线性时间排序
     */
    public static void countSort(int[] num) {

        //找出待排序数组最大、最小值
        int min, max;
        min = max = num[0];
        for (int i = 1; i < num.length; i++) {
            if (num[i] < min) {
                min = num[i];
            } else if (num[i] > max) {
                max = num[i];
            }
        }
        //定义数组B存放排好的数
        int[] result = new int[num.length];
        //定义数组C，大小为（max-min+1）,C[i]为A中值为i的个数
        int[] counter = new int[max - min + 1];
        for (int i = 0; i < max - min + 1; i++) {
            counter[i] = 0;
        }
        for (int aNum : num) {
            //计数
            counter[aNum - min]++;
        }
        for (int i = 1; i < max - min + 1; i++) {
            //累加
            counter[i] += counter[i - 1];
        }
        for (int i = num.length - 1; i >= 0; i--) {
            //A中值倒序取出放到B中合适位置，并在C计数中减1
            result[counter[num[i] - min] - 1] = num[i];
            //因数组下标从0开始，所以减1
            counter[num[i] - min]--;
        }

        num = result;
    }

    /**
     * 基数排序(桶排序)
     */
    public static void radixSort(int[] array, int d) {
        int n = 1;//代表位数对应的数：1,10,100...
        int k = 0;//保存每一位排序后的结果用于下一位的排序输入
        int length = array.length;
        int[][] bucket = new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order = new int[length];//用于保存每个桶里有多少个数字
        while (n < d) {
            for (int num : array) //将数组array里的每个数字放在相应的桶里
            {
                int digit = (num / n) % 10;
                bucket[digit][order[digit]] = num;
                order[digit]++;
            }
            for (int i = 0; i < length; i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
            {
                if (order[i] != 0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                {
                    for (int j = 0; j < order[i]; j++) {
                        array[k] = bucket[i][j];
                        k++;
                    }
                }
                order[i] = 0;//将桶里计数器置0，用于下一次位排序
            }
            n *= 10;
            k = 0;//将k置0，用于下一轮保存位排序结果
        }

    }

    /**
     * 基数排序(桶排序)
     */
    public static void radixSort(int[] data, int radix, int d) {
        // 缓存数组
        int[] tmp = new int[data.length];
        // buckets用于记录待排序元素的信息
        // buckets数组定义了max-min个桶
        int[] buckets = new int[radix];

        for (int i = 0, rate = 1; i < d; i++) {

            // 重置count数组，开始统计下一个关键字
            Arrays.fill(buckets, 0);
            // 将data中的元素完全复制到tmp数组中
            System.arraycopy(data, 0, tmp, 0, data.length);

            // 计算每个待排序数据的子关键字
            for (int j = 0; j < data.length; j++) {
                int subKey = (tmp[j] / rate) % radix;
                buckets[subKey]++;
            }

            for (int j = 1; j < radix; j++) {
                buckets[j] = buckets[j] + buckets[j - 1];
            }

            // 按子关键字对指定的数据进行排序
            for (int m = data.length - 1; m >= 0; m--) {
                int subKey = (tmp[m] / rate) % radix;
                data[--buckets[subKey]] = tmp[m];
            }
            rate *= radix;
        }

    }

    private static void printArray(int[] num) {
        for (int n : num) {
            System.out.printf(n + "\t");
        }
        System.out.println();

    }

    /**
     * 堆排序，构建最大堆
     */
    public static void heap_sort(int[] num) {
        int length = num.length;
        int i, temp;
        //bulid max heap
        HeapUtils.build_max_heap(num, length);
        i = length;
        //exchange the first value to the last unitl i=1
        while (i > 1) {
            temp = num[i - 1];
            num[i - 1] = num[0];
            num[0] = temp;
            i--;
            //adjust max heap,make sure the fisrt value is the largest
            HeapUtils.adjust_max_heap(num, i, 1);
        }
    }

}
